/**
 * 亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
 * <p>
 * 亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
 * <p>
 * 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
 * <p>
 * 游戏一直持续到所有石子都被拿走。
 * <p>
 * 假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
 * <p>
 *  
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(stoneGame(new int[]{3, 9, 3, 1, 3, 1, 3, 1, 3, 1}));
    }

    private static int[] array;
    private static int[][] dp;

    public static int stoneGame(int[] piles) {
        array = piles;
        dp = new int[piles.length][piles.length];
        int all = 0;
        for (int value : array) {
            all += value;
        }
        int res = loop(all, 0, array.length - 1);
        return Math.max(res, all - res);
    }

    /**
     * 返回i到j内，先手的最大值
     *
     * @param i
     * @param j
     * @return
     */
    private static int loop(int all, int i, int j) {
        if (i == j) {
            return array[i];
        }
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int chooseLeft = all - loop(all - array[i], i + 1, j);
        int chooseRight = all - loop(all - array[j], i, j - 1);
        dp[i][j] = Math.max(chooseLeft, chooseRight);
        return dp[i][j];
    }
}